#include <bits/stdc++.h>

#define in read()
#define fi first
#define se second
#define pb push_back

using namespace std;

typedef long long ll;
typedef double db;
typedef vector < int > vec;
typedef pair < int , int > pii;

int read() {
    int x = 0; bool f = 0; char ch = getchar(); while(!isdigit(ch)) f |= ch == '-',ch = getchar();
    while(isdigit(ch)) x = x * 10 + (ch ^ 48),ch = getchar(); return f ? -x : x;
}

const int N = 1e5 + 10;

int n,m;
int pos[N];
char s[N];
int rt[N << 1];

namespace seg {
    const int L = 1e7 + 10;
    int ch[L][2],val[L],ndn;
    void upd(int &x,int pos,int l = 1,int r = n) {
	if(!x) x = ++ndn; val[x]++; if(l == r) return; int mid = l + r >> 1;
	if(pos <= mid) upd(ch[x][0],pos,l,mid); else upd(ch[x][1],pos,mid + 1,r);
    }
    int query(int x,int xl,int xr,int l = 1,int r = n) {
	if(!x) return 0; if(xl == l && xr == r) return val[x]; int mid = l + r >> 1;
	if(xr <= mid) return query(ch[x][0],xl,xr,l,mid); else if(xl > mid) return query(ch[x][1],xl,xr,mid + 1,r);
	else return query(ch[x][0],xl,mid,l,mid) + query(ch[x][1],mid + 1,xr,mid + 1,r);
    }
    int merge(int x,int y,int l = 1,int r = n) {
	if(!x || !y) return x | y; int z = ++ndn; val[z] = val[x] + val[y]; if(l == r) return z; int mid = l + r >> 1;
	ch[z][0] = merge(ch[x][0],ch[y][0],l,mid); ch[z][1] = merge(ch[x][1],ch[y][1],mid + 1,r); return z;
    }
}

template < int N >
    struct SAM {
    int ch[N][26],link[N],lst,ndn,len[N],f[21][N];
    vec G[N];
    SAM() { ndn = 0; lst = 0; memset(ch,0,sizeof ch); link[0] = -1; len[0] = 0; }
    void extend(int x) {
	int cur = ++ndn,p = lst; lst = cur; len[cur] = len[p] + 1;
	while(~p && !ch[p][x]) ch[p][x] = cur,p = link[p]; if(!~p) return link[cur] = 0,void();
	int q = ch[p][x]; if(len[q] == len[p] + 1) return link[cur] = q,void();
	int clo = ++ndn; len[clo] = len[p] + 1; for(int i = 0;i < 26;i++) ch[clo][i] = ch[q][i]; link[clo] = link[q];
	while(~p && ch[p][x] == q) ch[p][x] = clo,p = link[p]; link[cur] = link[q] = clo;
    }
    void dfs(int x) {
	for(int i = 1;i < 20;i++) f[i][x] = f[i - 1][f[i - 1][x]];
	for(auto y : G[x]) f[0][y] = x,dfs(y),rt[x] = seg :: merge(rt[x],rt[y]);
    }
    void build(char *s) {
	int l = strlen(s + 1); for(int i = 1;i <= l;i++) extend(s[i] - 'a'),seg :: upd(rt[lst],i),pos[i] = lst;
	for(int i = 1;i <= ndn;i++) G[link[i]].pb(i);
	dfs(0);
    }
    bool check(int mid,int a,int b,int c,int d) {
	int p = pos[c + mid - 1];
	for(int i = 19;i >= 0;i--) if(len[f[i][p]] >= mid) p = f[i][p];
	return seg :: query(rt[p],a + mid - 1,b) > 0;
    }
    void solve() {
	int a = in,b = in,c = in,d = in;
	int l = 1,r = min(b - a + 1,d - c + 1),ans = 0;
	while(l <= r) {
	    int mid = l + r >> 1;
	    if(check(mid,a,b,c,d)) ans = mid,l = mid + 1;
	    else r = mid - 1;
	}
	printf("%d\n",ans);
    }
};

SAM < N << 1 > T;

int main() {
#ifndef ONLINE_JUDGE
    freopen("1.in","r",stdin);
#endif
    n = in,m = in; scanf("%s",s + 1); T.build(s); 
    for(int i = 1;i <= m;i++) T.solve(); return 0;
}
